package org.jkuang.qstar.index.iterator;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 采用优先队列最大或最小堆算法
 * 
 * 当元素不重复时候 算法效率 O(logN) 当元素大量重复时候算法效率O(N*logN)
 * 
 * @author jkuang
 * 
 * @param <E>
 */
public class TSQueue<E> implements TSIterator<E> {

	private TSIterator<E>[] queue;
	private int size = 0;
	private E tempNode;
	private E distincNode;
	private boolean desc;
	private Comparator<E> comparator;

	public TSQueue(int initialCapacity, boolean desc) {

		this(initialCapacity, null, desc);
	}

	@SuppressWarnings("unchecked")
	public TSQueue(int initialCapacity, Comparator<E> comparator, boolean desc) {

		if (initialCapacity < 1)
			throw new IllegalArgumentException();
		this.queue = new TSIterator[initialCapacity];
		this.desc = desc;
		this.comparator = comparator;
	}

	/**
	 * 自动增长扩容
	 * 
	 * @param minCapacity
	 */
	private void grow(int minCapacity) {
		if (minCapacity < 0) // overflow
			throw new OutOfMemoryError();
		int oldCapacity = queue.length;
		// Double size if small; else grow by 50%
		int newCapacity = ((oldCapacity < 64) ? ((oldCapacity + 1) * 2) : ((oldCapacity / 2) * 3));
		if (newCapacity < 0) // overflow
			newCapacity = Integer.MAX_VALUE;
		if (newCapacity < minCapacity)
			newCapacity = minCapacity;
		queue = Arrays.copyOf(queue, newCapacity);
	}

	/**
	 * 
	 * @param e
	 * @return
	 */
	public boolean add(TSIterator<E> e) {
		if (e == null || !e.hasNext()) {
			return false;
		}
		int i = size;
		if (i >= queue.length)
			grow(i + 1);
		size = i + 1;
		if (i == 0)
			queue[0] = e;
		else
			siftUpComparable(i, e);
		return true;
	}

	public int size() {
		return size;
	}

	/**
	 * 
	 * @param i
	 * @return
	 */
	private TSIterator<E> removeAt(int i) {
		assert i >= 0 && i < size;
		int s = --size;
		if (s == i) // removed last element
			queue[i] = null;
		else {
			TSIterator<E> moved = queue[s];
			queue[s] = null;
			siftDownComparable(i, moved);
			if (queue[i] == moved) {
				siftUpComparable(i, moved);
				if (queue[i] != moved)
					return moved;
			}
		}
		return null;
	}

	/**
	 * 
	 * @param k
	 * @param x
	 */
	private void siftUpComparable(int k, TSIterator<E> x) {
		TSIterator<E> key = x;
		while (k > 0) {
			int parent = (k - 1) >>> 1;
			TSIterator<E> e = queue[parent];
			if (key.compareTo(e) >= 0)
				break;
			queue[k] = e;
			k = parent;
		}
		queue[k] = key;
	}

	/**
	 * 
	 * @param k
	 * @param key
	 */
	private void siftDownComparable(int k, TSIterator<E> key) {

		int half = size >>> 1; // loop while a non-leaf
		while (k < half) {
			int child = (k << 1) + 1; // assume left child is least
			TSIterator<E> c = queue[child];
			int right = child + 1;
			if (right < size && c.compareTo(queue[right]) > 0)
				c = queue[child = right];
			if (key.compareTo(c) <= 0)
				break;
			queue[k] = c;
			k = child;
		}
		queue[k] = key;
	}

	/**
	 * 
	 * @return
	 */
	public boolean hasNext() {
		if (this.tempNode != null) {
			return true;
		}
		while (this.size > 0) {
			TSIterator<E> result = queue[0];
			E nodeEnty = result.next();
			boolean virtual = result.isVirtual();

			if (!result.hasNext()) {
				removeAt(0);
			} else if (size > 1) {
				siftDownComparable(0, result);
			}
			// 非虚拟值
			if (!virtual && distincNode != nodeEnty) {
				this.distincNode = nodeEnty;
				this.tempNode = nodeEnty;
				return true;
			}
		}
		return false;
	}

	/**
	 * 
	 * @return
	 */
	public E next() {
		E tmpe = this.tempNode;
		this.tempNode = null;
		return tmpe;
	}

	@Override
	public E peek() {
		// TODO Auto-generated method stub
		return this.tempNode;
	}

	@Override
	public boolean isVirtual() {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int scanSize() {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public int compareTo(TSIterator<E> o) {
		// TODO Auto-generated method stub
		if (desc) {
			return -comparator.compare(this.peek(), o.peek());
		} else {
			return comparator.compare(this.peek(), o.peek());
		}

	}

}
